package leetcode.hot100;

import java.util.Stack;

public class MaxRectArea {


    public static void main(String[] args) {

        char[][] matrix = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
        System.out.println(maximalSquare(matrix));

    }

    public static int maximalSquare(char[][] matrix) {
        //动态规划,dp[i,j]表示以i,j为右下角的最大全1正方形边长，复杂度O(m*n)
        int row = matrix.length, col = matrix[0].length;
        int[][] dp = new int[row][col];
        int max = 0;
        //初始化边
        for (int i = 0; i < row; i++) {
            dp[i][0] = matrix[i][0]=='1'?1:0;
            max = max|dp[i][0];
        }
        for (int j = 0; j < col; j++) {
            dp[0][j] = matrix[0][j]=='1'?1:0;
            max = max|dp[0][j];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if(matrix[i][j]=='1'){
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                    max = Math.max(dp[i][j],max);
                }
            }
        }
        return max*max;
    }

    public int maximalSquare1(char[][] matrix) {
        //求最大矩形面积的做法，时间复杂度O(m*n)
        int max = 0;
        int[] height = new int[matrix[0].length];
        //计算每一行
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < height.length; j++) {
                if(matrix[i][j]=='1') height[j]++;
                else height[j] = 0;
            }
            max = Math.max(max,maxRectArea(height));
        }
        return max*max;
    }

    public static int maxRectArea(int[] height){
        //返回每个矩形长宽最小者
        //在两端补0
        int max = 0, len = height.length;
        Stack<Integer> stack = new Stack<>(); //单增栈，入栈时把比入栈元素小的都出栈，这里存的是下标
        int[] padHeight = new int[len+2];
        System.arraycopy(height,0,padHeight,1,len);
        stack.push(0);
        for (int i = 1; i < padHeight.length; i++) {
            while (padHeight[i]<padHeight[stack.peek()]){//要把大的出栈,可能同时多个需要出栈
                int high = padHeight[stack.pop()];
                //求以high为高的矩形右端,可能有和high重复高度的，删去
                while (padHeight[stack.peek()]==high) stack.pop();
                //此时栈顶就是high为高的矩形右端
                int wide = i-stack.peek()-1;
                max = Math.max(max, Math.min(high,wide));
            }
            stack.push(i);
        }
        return max;
    }
}
